<?php
//堆排序算法
// 把array中前n个元素的第i个节点（及其子节点）修正为大堆顶
function heap_adjust($i, $n, &$arr){
	array_unshift($arr, 0);
	while(2 * $i <= $n){
		$lchild_index = 2 * $i;
		$max_child_index = $lchild_index; //先假设左节点最大
		if($lchild_index + 1 <= $n && $arr[$lchild_index + 1] > $arr[$lchild_index]){
			$max_child_index = $lchild_index + 1; //存在右节点，并且右节点最大
		}
		//已经得出最大节点了，接下来和自己的根比较
		if($arr[$max_child_index] > $arr[$i]){
			$temp = $arr[$i];
			$arr[$i] = $arr[$max_child_index];
			$arr[$max_child_index] = $temp;
			$i = $max_child_index;
		}else{
			break;
		}
	}
	array_shift($arr);
}

//堆排序：先得到纯大顶堆，然后循环排序。需要heap_adjust()发放支持
function heap_sort($arr){
	//从$n/2开始到1， 逐个修正为大堆顶
	$n = count($arr);
	for($i=floor($n/2);$i>0;$i--){
		heap_adjust($i, $n, $arr);
	}
	
	//循环排序，每次得到纯大顶堆后，把根换到有序区
	// array_unshift($arr, 0);
	for($m=$n-1;$m>=1;$m--){
		$temp = $arr[0];
		$arr[0] = $arr[$m];
		$arr[$m] = $temp;
		heap_adjust(1, $m, $arr);
	}
	return $arr;
}

$arr = [30, 20, 80, 40, 50, 10, 60, 70, 90, 22];
$arr = [45, 48, 74, 58, 96, 21, 45, 88, 75, 36, 95, 84, 15];
echo "原始数据：--------------------------<br>";
echo "<pre>";
print_r($arr);
echo "</pre>";

echo "堆排序：--------------------------<br>";
$arr_sort = heap_sort($arr);
echo "<pre>";
print_r($arr_sort);
echo "</pre>";

?>